from importlib.resources import path
from typing import List


class Solution:
    def permutation(self, s: str) -> List[str]:

        ans = []
        path = []
        visited = [False for _ in range(len(s))]
        chs = sorted(list(s))
        
        def dfs(path, visited):
            if len(path) == len(s):
                ans.append("".join(path))
                return
            
            for i in range(len(s)):
                if visited[i] or (i>0 and not visited[i-1] and chs[i]==chs[i-1]):
                    continue
                visited[i]=True
                path.append(chs[i])
                dfs(path, visited)
                visited[i]=False
                path.pop()
        dfs(path, visited)
        return ans


if __name__ == '__main__':
    a = Solution().permutation("aba")
    print(a)